package gold.digger;

import gold.utils.InputUtil;
import gold.utils.UF;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1102 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        /**
         * Created by fanzhenyu02 on 2020/6/27.
         * Union Find 算法实现
         */
        public class UF {
            // 连通分量个数
            private int count;
            // 存储一棵树
            private int[] parent;
            // 记录树的“重量”
            private int[] size;

            public UF(int n) {
                this.count = n;
                parent = new int[n];
                size = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    size[i] = 1;
                }
            }

            /* 将 p 和 q 连接 */
            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ)
                    return;

                // 小树接到大树下面，较平衡
                if (size[rootP] > size[rootQ]) {
                    parent[rootQ] = rootP;
                    size[rootP] += size[rootQ];
                } else {
                    parent[rootP] = rootQ;
                    size[rootQ] += size[rootP];
                }
                count--;
            }

            /* 判断 p 和 q 是否连通 */
            public boolean connected(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                return rootP == rootQ;
            }

            private int find(int x) {
                while (parent[x] != x) {
                    // 进行路径压缩
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            /* 返回图中有多少个连通分量 */
            public int count() {
                return count;
            }

            /* 返回图中联通集合 */
            public Map<Integer, List<Integer>> outputAggregateSet(int n) {
                Map<Integer, List<Integer>> aggregateMap = new HashMap<>();

                // 共有n个集合
                for (int i = 0; i < n; i++) {
                    int parentId = find(i);
                    if (!aggregateMap.containsKey(parentId)) aggregateMap.put(parentId, new ArrayList<>());
                    aggregateMap.get(parentId).add(i);
                }

                System.out.println(aggregateMap.toString());
                return aggregateMap;
            }
        }

        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        public int maximumMinimumPath(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE, mid = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    left = Math.min(left, grid[i][j]);
                    right = Math.max(right, grid[i][j]);
                }
            }


            while (left < right) {
                mid = left + (right - left) / 2;
                if (checkValid(grid, mid)) {
                    // 当前mid可行，就增大left
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            if (checkValid(grid, left)) return left;
            else return left - 1;
        }

        public boolean checkValid(int[][] grid, int pathVal) {
            int m = grid.length, n = grid[0].length;
            UF uf = new UF(m * n);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] >= pathVal) {
                        for (int[] direction : directions) {
                            int nextRow = i + direction[0], nextCol = j + direction[1];
                            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || grid[nextRow][nextCol] < pathVal) {
                                continue;
                            }

                            uf.union(i * n + j, nextRow * n + nextCol);// 并查联通
                        }
                    }
                }
            }

            return uf.connected(0, m * n - 1);
        }

    }


    class Solution_Wrong_Thought_Second {
        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        Map<String, Integer> memo = new HashMap<>();
        int m = 0, n = 0;

        public int maximumMinimumPath(int[][] grid) {
            m = grid.length;
            n = grid[0].length;
            return dfs(grid, m - 1, n - 1, new HashSet<>());
        }

        public int dfs(int[][] grid, int row, int col, Set<String> visitedPath) {
            String curNodeKey = row + "," + col;
            if (memo.containsKey(curNodeKey)) return memo.get(curNodeKey);
            if (row == 0 && col == 0) return grid[0][0];
            visitedPath.add(curNodeKey);

            int curNodeAns = Integer.MIN_VALUE;
            for (int[] direction : directions) {
                int nextRow = row + direction[0], nextCol = col + direction[1];
                if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visitedPath.contains(nextRow + "," + nextCol)) {
                    continue;
                }
                visitedPath.add(nextRow + "," + nextCol);
                int nextAns = dfs(grid, nextRow, nextCol, visitedPath);
                curNodeAns = Math.min(grid[row][col], Math.max(nextAns, curNodeAns));
                visitedPath.remove(nextRow + "," + nextCol);
            }

            memo.put(curNodeKey, curNodeAns);
            visitedPath.remove(curNodeKey);
            return curNodeAns;
        }
    }

    class Solution_Wrong_Thought {

        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        public int maximumMinimumPath(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] dp = new int[m][n];
            boolean[][] visited = new boolean[m][n];
            Queue<Integer> queue = new LinkedList<>();
            queue.add(0);
            dp[0][0] = grid[0][0];
            visited[0][0] = true;

            while (!queue.isEmpty()) {
                int size = queue.size();
                Set<Integer> curLoopCandidateSet = new HashSet<>();

                for (int i = 0; i < size; i++) {
                    int cur = queue.poll(), curRow = cur / n, curCol = cur % n;
                    for (int[] direction : directions) {
                        int nextRow = curRow + direction[0], nextCol = curCol + direction[1];
                        if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol])
                            continue;

                        // grid[curRow][curCol] 已经存储到达此节点的所有路径 最大化的 最小值
                        // grid[nextRow][nextRow] 只需要和之前已有节点进行比较即可
                        dp[nextRow][nextCol] = Math.min(grid[nextRow][nextCol], Math.max(dp[nextRow][nextCol], dp[curRow][curCol]));
                        curLoopCandidateSet.add(nextRow * n + nextCol);
                    }
                }

                // 开始遍历 curLoopCandidateSet 加入 queue
                for (Integer idx : curLoopCandidateSet) {
                    queue.add(idx);
                    visited[idx / n][idx % n] = true;
                }

                curLoopCandidateSet.clear();
            }

            return dp[m - 1][n - 1];
        }
    }

    public void run() {
        System.out.println(new Solution().maximumMinimumPath(InputUtil.toDoubleIntegerArray("[[5,4,5],[1,2,6],[7,4,6]]")));
        System.out.println(new Solution().maximumMinimumPath(InputUtil.toDoubleIntegerArray("[[2,2,1,2,2,2],[1,2,2,2,1,2]]")));
        System.out.println(new Solution().maximumMinimumPath(InputUtil.toDoubleIntegerArray("[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]")));
        System.out.println(new Solution().maximumMinimumPath(InputUtil.toDoubleIntegerArray("[[1,0,1,1,1,0,0],[0,1,1,1,1,1,0],[1,0,1,1,1,1,0],[1,1,1,0,1,1,0],[1,0,1,1,0,1,0]]")));
        System.out.println(new Solution().maximumMinimumPath(InputUtil.toDoubleIntegerArray("[[5,4,3,1],[7,4,5,2],[4,9,8,2],[2,3,6,6]]")));
    }

    public static void main(String[] args) throws Exception {
        LC1102 an = new LC1102();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
